# 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
#
#  有效 二叉搜索树定义如下：
#  节点的左子树只包含 小于 当前节点的数。
#  节点的右子树只包含 大于 当前节点的数。
#  所有左子树和右子树自身必须也是二叉搜索树。
#
#  示例 1：
# 输入：root = [2,1,3]
# 输出：true
#
#  示例 2：
# 输入：root = [5,1,4,null,null,3,6]
# 输出：false
# 解释：根节点的值是 5 ，但是右子节点的值是 4 。
import sys
from com.example.tree.tree_node import TreeNode


class Solution:

    def isValidBST3(self, root: TreeNode) -> bool:
        def check(node: TreeNode, lower: int, upper: int) -> bool:
            if node is None:
                return True
            left_res, right_res = check(node.left, lower, node.val), check(node.right, node.val, upper)
            if node.val <= lower or node.val >= upper:
                return False
            return left_res and right_res
        return check(root, -sys.maxsize, sys.maxsize)

    def isValidBST2(self, root: TreeNode) -> bool:
        """
        中序遍历
        当前元素值大于上一个元素值
        :param root:
        :return:
        """
        self.pre = -sys.maxsize - 1  # 记录上一个值

        def inorder(root: TreeNode) -> bool:
            if not root:
                return True
            leftRes = inorder(root.left)
            if self.pre >= root.val:
                return False
            self.pre = root.val
            rightRes = inorder(root.right)
            return leftRes and rightRes

        return inorder(root)

    def isValidBST1(self, root: TreeNode) -> bool:
        def postOrder(root: TreeNode) -> (int, int, bool):
            """
            后序遍历方式
            BST = 左子树最大值 < 根结点值 < 右子树最小值
            :param root:
            :return: minVal, maxVal, isBST
            """
            if not root:
                return None
            leftRes = postOrder(root.left)
            rightRes = postOrder(root.right)
            # BST = 左子树最大值 < 根结点值 + 右子树最小值> 根结点值
            if leftRes and (not leftRes[2] or leftRes[1] >= root.val):  # 不是BST的情况1
                return sys.maxsize, -sys.maxsize - 1, False
            if rightRes and (not rightRes[2] or rightRes[0] <= root.val):  # 不是BST的情况2
                return sys.maxsize, -sys.maxsize - 1, False
            minVal = leftRes[0] if leftRes else root.val  # 更新当前二叉树的最小值
            maxVal = rightRes[1] if rightRes else root.val  # 更新当前二叉树的最大值
            return minVal, maxVal, True

        res = postOrder(root)
        if not res:
            return True
        return postOrder(root)[2]

    def isValidBST(self, root: TreeNode) -> bool:
        return self.isValidBST1(root)


if __name__ == "__main__":
    #                    5
    #            3                6
    #        2        4                 7
    #    0
    # -1    1
    # root = TreeNode(5)
    # root.left, root.right = TreeNode(3), TreeNode(6)
    # root.left.left, root.left.right, root.right.right = TreeNode(2), TreeNode(4), TreeNode(7)
    # root.left.left.left = TreeNode(0)
    # root.left.left.left.left, root.left.left.left.right = TreeNode(-1), TreeNode(1)

    root = TreeNode(5)
    root.left, root.right = TreeNode(1), TreeNode(4)
    root.right.left, root.right.right = TreeNode(3), TreeNode(6)
    print(Solution().isValidBST(root))
